package com.lsa.letcode.the75.sortColors;

/**
|
2 2 2 0 1 0 1 0 0 0 2 2 2 1 1 0 2
|                             |

                  |
0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 2 2
            |     |
            
High level idea - 
leftPtr -> insertion point for the next '0'
rigthPtr -> insertion point for the next '2'

runnerPtr -> runs between leftPtr and rigthPtr, takes el, insert it whether '0' or '2'. 
After runnerPtr==rigthPtr - all elements was checked - all elements between leftPtr and rigthPtr are '1'.        
 */
public class Solution {
    public void sortColors(int[] nums) {
    	if (nums.length == 0) {
    		return;
    	}
        int len = nums.length;
        int idx0 = 0; // next insertion idx for the '0'
		int idx2 = len - 1; // next insertion idx for the '2'
        
        while(idx0 < len && nums[idx0] == 0) {
        	idx0++;
        }
        
        if (idx0 == len){ // all '0'
        	return;
        }
        
        while(idx2 > idx0 && nums[idx2] == 2) {
        	idx2--;
        }
        
        if (idx2 == idx0){ // all '2'
        	return;
        }

        int idx = idx0;
        int d = 1;
        for (;idx < idx2 + 1;) {
        	if (d == 1) {
        		d = nums[idx];
        		nums[idx] = 1;
        	}
        	if (d == 2) {
        		int t = nums[idx2];
        		nums[idx2] = d;
        		d = t;
        		
        		// skip all '2' - they are at correct position
        		while(idx2 > idx0 && nums[idx2] == 2) { 
        			idx2--;
        		}
        	}
        	else if (d == 0){ 
        		int t = nums[idx0];
        		nums[idx0++] = d;
        		d = t;
        		
        		// skip all '0' - they are at correct position
        		while(idx0 < idx2 + 1 && nums[idx0] == 0) {
                	idx0++;
                }
        	}
        	
        	if (d == 1) {
        		idx = Math.max(idx + 1, idx0);
        	}
		}
    }
}